/*
Id:[64]	
分苹果 (15分)
题目内容:
把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？M, N为自然数。说明：如有7个苹
果，3个盘子，则(5, 1, 1)和(1, 5, 1)和(1, 1, 5)都是同一种分法。
输入描述:
第一行一个整数表示数据的组数（多组数据），对于每组数据第一行是苹果个数M (1 ≤ m ≤ 100) ，第二行是盘子个数N(1 ≤ 
n ≤ 100)。
输出描述:
每组数据输出一行,放苹果的方法个数。
输入样例:
1 
3 
2
输出样例:
2
*/

/*
 * 由于1 1 5 和 5 1 1算作一种情况，所以在所有情况中，左盘的苹果数一定大于右边的苹果数
 *
 * 苹果数m, 盘子数n
 * 1. m < n, 当每个盘子只放一个苹果时，含有空盘子，空盘子不影响方法数, 可以去掉，f(m, m)
 * 2. m >= n, 如果把苹果放入盘子后，含有空盘子，一个个去掉 f(m, n - 1)
 *			  如果每个盘子都有苹果，全部拿掉一个苹果，对方法数没有影响，f(m - n, n)
 *		该情况总的方法数f(m, n - 1) + f(m - n, n)
 * 3. 当苹果数为０时，算一种方法, 当盘子只剩一个时，只有一种方法
 *
 */

#include <iostream> 
using namespace std;

int f(int m, int n){
	if(m == 0 || n == 1){
		return 1;
	}
	if(m < n)
		return f(m, m);
	else
		return f(m - n, n) + f(m, n - 1);
}

int main(){
	int T;
	cin >> T;
	while(T--){
		int m, n;
		cin >> m >> n;
		cout << f(m, n) << endl;
	}
    return 0;
}
